/*
 * @lc app=leetcode id=55 lang=cpp
 *
 * [55] Jump Game
 */
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        if (len < 1) {
            return true;
        }

        int right = nums[0];
        int lastRight = -1;

        while (lastRight != right) {
            lastRight = right;

            for (int i=0; i<=right; i++) {
                if (right >= len-1) {
                    return true;
                }
                right = std::max(i+nums[i], right);
            }
        }

        return false;
    }
};

